package lt172
/*
172. 阶乘后的零
给定一个整数 n ，返回 n! 结果中尾随零的数量。
提示 n! = n * (n - 1) * (n - 2) * ... * 3 * 2 * 1

进阶：你可以设计并实现对数时间复杂度的算法来解决此问题吗？
*/
/*
计算阶乘 ，不过阶乘结果可能非常大 
对数时间复杂度，则不能求阶乘

计算N!中有多少个10 ，即计算有多少对2和5（分解质因数）
最后结果即 2 的个数和 5 的个数取较小值。
每两个数字就会多一个质因数 2，而每五个数字才多一个质因数 5。
每 5 个数字就会多一个质因数 5。

0~4 的阶乘里没有质因数 5，
5~9 的阶乘里有 1 个质因数 5，
10~14 的阶乘里有 2 个质因数 5，依此类推。

所以 0 的个数即为 `min(阶乘中 5 的个数和 2 的个数)`。
- N! 有多少个后缀 0，即 N! 有多少个质因数 5。
N! 有多少个质因数 5，即 N 可以划分成多少组 5个数字一组，
加上划分成多少组 25 个数字一组，
加上划分多少组成 125 个数字一组，等等。

即 `res = N/5 + N/(5^2) + N/(5^3) + ... = ((N / 5) / 5) / 5 /...` 。最终算法复杂度为 O(logN)。
*/
func trailingZeroes(n int) int {
	if n/5 == 0 {
		return 0
	}
	return n/5 + trailingZeroes(n/5)
}